{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Remoteness of All Cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumRemoteness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有单元格的远离程度之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个下标从 <strong>0</strong> 开始的大小为 <code>n * n</code> 的矩阵 <code>grid</code>，其中每个单元格的值 <code>grid[i][j]</code> 要么是 <strong>正整数</strong>，要么是表示阻塞单元格的值 <code>-1</code> 。</p>\n",
    "\n",
    "<p>你可以从一个非阻塞单元格移动到与其共享边的任何非阻塞单元格。</p>\n",
    "\n",
    "<p>对于任何单元格 <code>(i, j)</code>，我们定义其 <strong>远离程度</strong> <code>R[i][j]</code> 如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果单元格 <code>(i, j)</code> 是 <strong>非阻塞</strong> 单元格，则 <code>R[i][j]</code> 是值 <code>grid[x][y]</code> 的总和，其中 <strong>没有</strong> 从 <strong>非阻塞</strong> 单元格 <code>(x, y)</code> 到单元格 <code>(i, j)</code> 的路径。</li>\n",
    "\t<li>对于阻塞单元格，<code>R[i][j] == 0</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回所有单元格的 <code>R[i][j]</code> 之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/09/12/1-new.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 400px; height: 304px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[-1,1,-1],[5,-1,4],[-1,3,-1]]\n",
    "<b>输出：</b>39\n",
    "<b>解释：</b>在上面的图片中，有四个矩阵。左上角的矩阵是题目给定矩阵的初始值。被阻塞的单元格是黑色的，其他单元格的值与输入相同。在右上方的网格中，可以看到所有单元格的值也就是 R[i][j] 的值。答案是它们的和。即:0 + 12 + 0 + 8 + 0 + 9 + 0 + 10 + 0 = 39。\n",
    "在上图左下角的矩阵，计算 R[0][1] (目标单元格为绿色)。我们应该将单元格 (0,1) 无法到达的单元格的值相加。这些单元格在这个矩阵中是黄色的。所以 R[0][1] = 5 + 4 + 3 = 12。\n",
    "在上图右下角的矩阵，计算 R[1][2] (目标单元格为绿色)。我们应该把单元格 (1,2) 无法到达的单元格的值相加。这些单元格在这个矩阵中是黄色的。所以 R[1][2] = 1 + 5 + 3 = 9。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/09/12/2.png\" style=\"width: 400px; height: 302px; background: #fff; border-radius: .5rem;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[-1,3,4],[-1,-1,-1],[3,-1,-1]]\n",
    "<b>输出：</b>13\n",
    "<b>解释：</b>在上面的图片中，有四个矩阵。左上角的矩阵是给定矩阵的初始值。被阻塞的单元格是黑色的，其他单元格的值与输入相同。在右上方的网格中，可以看到所有单元格的值也就是 R[i][j] 的值。答案是它们的和。即:3 + 3 + 0 + 0 + 0 + 0 + 7 + 0 + 0 = 13。\n",
    "在上图左下角的矩阵上，计算 R[0][2] (目标单元格为绿色)。将单元格 (0,2) 无法到达的单元格的值相加。这个单元格在这个矩阵中是黄色的。所以 R[0][2] = 3。\n",
    "在上图右下角的矩阵上，计算 R[2][0] (目标单元格为绿色)。将单元格 (2,0) 无法到达的单元格的值相加，这些单元格在这个矩阵中是黄色的。所以 R[2][0] = 3 + 4 = 7。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>因为除了 (0,0) 没有其他单元格，所以 R[0][0] 等于 0。所以所有单元格的和是 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code> 或&nbsp;<code>grid[i][j] == -1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-remoteness-of-all-cells](https://leetcode.cn/problems/sum-of-remoteness-of-all-cells/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-remoteness-of-all-cells](https://leetcode.cn/problems/sum-of-remoteness-of-all-cells/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-1,1,-1],[5,-1,4],[-1,3,-1]]', '[[-1,3,4],[-1,-1,-1],[3,-1,-1]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [*range(n)]\n",
    "        self.rank = [1] * n\n",
    "        self.n = n\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def check(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def union(self, x, y):  # rank by deep\n",
    "        x_0 = self.find(x)\n",
    "        y_0 = self.find(y)\n",
    "        if x_0 != y_0:\n",
    "            if self.rank[x_0] < self.rank[y_0]:\n",
    "                self.parent[x_0] = y_0\n",
    "            elif self.rank[x_0] > self.rank[y_0]:\n",
    "                self.parent[y_0] = x_0\n",
    "            else:\n",
    "                self.rank[x_0] += 1\n",
    "                self.parent[y_0] = x_0\n",
    "            self.n -= 1\n",
    "\n",
    "D = [0, 1, 0, -1, 0]\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, G: List[List[int]]) -> int:\n",
    "        n = len(G)\n",
    "\n",
    "        us = UnionSet(n * n)\n",
    "\n",
    "        tot = res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if G[i][j] != -1:\n",
    "                    tot += G[i][j]\n",
    "                    if i and G[i - 1][j] != -1:\n",
    "                        us.union(i * n + j, i * n + j - n)\n",
    "                    if j and G[i][j - 1] != -1:\n",
    "                        us.union(i * n + j, i * n + j - 1)\n",
    "        \n",
    "        book = defaultdict(int)\n",
    "        cnt = defaultdict(int)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if G[i][j] == -1:\n",
    "                    continue\n",
    "                book[us.find(i * n + j)] += G[i][j]\n",
    "                cnt[us.find(i * n + j)] += 1\n",
    "        \n",
    "        for t in book:\n",
    "            res += (tot - book[t]) * cnt[t]\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion:\n",
    "  def __init__(self, size):\n",
    "      self.parent = list(range(size))\n",
    "      self.rank=[1]*size\n",
    "      self.setCount=size\n",
    "      \n",
    "  def find(self,i):\n",
    "      if self.parent[i]==i:\n",
    "          return i\n",
    "      else:\n",
    "          self.parent[i]=self.find(self.parent[i])\n",
    "          return self.parent[i]\n",
    "          \n",
    "  def union(self,i,j):\n",
    "      x,y=self.find(i),self.find(j)\n",
    "      if x==y:\n",
    "          return\n",
    "      if self.rank[x]<self.rank[y]:\n",
    "          x,y=y,x\n",
    "      self.rank[x]+=self.rank[y]\n",
    "      self.parent[y]=x\n",
    "      self.setCount-=1\n",
    "      \n",
    "  def is_connected(self,i,j):\n",
    "      return self.find(i)==self.find(j)\n",
    "      \n",
    "  def get_partset(self):\n",
    "      \n",
    "      part=defaultdict(list)\n",
    "      for i in range(len(self.parent)):\n",
    "          part[self.find(i)].append(i)\n",
    "      return part\n",
    "      \n",
    "class Solution:\n",
    "  def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "      n=len(grid)\n",
    "      size,total=n*n,0\n",
    "      kkk=setUnion(size)\n",
    "      for i in range(n):\n",
    "          for j in range(n):\n",
    "              if grid[i][j]>0:\n",
    "                  for a,b in [(-1,0),(0,-1)]:\n",
    "                      cur_i,cur_j=i+a,j+b\n",
    "                      if cur_i<0 or cur_j<0 or grid[cur_i][cur_j]==-1:\n",
    "                          continue\n",
    "                      kkk.union(i*n+j,cur_i*n+cur_j)\n",
    "                  total+=grid[i][j] \n",
    "      x=defaultdict(int)\n",
    "      for i in range(n):\n",
    "          for j in range(n):\n",
    "              if grid[i][j]>0:\n",
    "                  x[kkk.find(i*n+j)]+=grid[i][j]\n",
    "      ans=0\n",
    "      for i in range(n):\n",
    "          for j in range(n):\n",
    "              if grid[i][j]>0:\n",
    "                  ans+=total-x[kkk.find(i*n+j)]\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:#并查集模板\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        pa, pb = self.find(a), self.find(b)\n",
    "        if pa != pb:\n",
    "            if self.size[pa] >= self.size[pb]:\n",
    "                self.size[pa] += self.size[pb]\n",
    "                self.p[pb] = pa\n",
    "            else:\n",
    "                self.size[pb] += self.size[pa]\n",
    "                self.p[pa] = pb\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n \n",
    "        uf = UnionFind(mn)\n",
    "\n",
    "        def idx(i, j):\n",
    "            return i * n + j \n",
    "        \n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "        \n",
    "        s = 0\n",
    "        que = Counter()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    s += grid[i][j]\n",
    "                    tmp = idx(i, j)\n",
    "                    for dx, dy in [[0, 1], [1, 0]]:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if valid(nx, ny) and grid[nx][ny] > 0:\n",
    "                            uf.union(tmp, idx(nx, ny))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    que[uf.find(idx(i, j))] += grid[i][j]\n",
    "        ans = 0\n",
    "        for k, v in que.items():\n",
    "            ans += (s - v) * uf.size[k]\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        size,total=n*n,0\n",
    "        kkk=setUnion(size)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    for a,b in [(-1,0),(0,-1)]:\n",
    "                        cur_i,cur_j=i+a,j+b\n",
    "                        if cur_i<0 or cur_j<0 or grid[cur_i][cur_j]==-1:\n",
    "                            continue\n",
    "                        kkk.union(i*n+j,cur_i*n+cur_j)\n",
    "                    total+=grid[i][j] \n",
    "        x=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    x[kkk.find(i*n+j)]+=grid[i][j]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    ans+=total-x[kkk.find(i*n+j)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        tot = 0\n",
    "        uf = UnionFind(n * n)\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] > 0:\n",
    "                    tot += grid[x][y]\n",
    "                    for dx,dy in [(-1,0),(0,-1)]:\n",
    "                        lx,ly = x + dx,y + dy\n",
    "                        if lx < 0 or lx >= n or ly < 0 or ly >= n or grid[lx][ly] < 0:\n",
    "                            continue\n",
    "                        uf.union(x * n + y,(x + dx) * n + y + dy)\n",
    "        ans = 0\n",
    "        rootval = defaultdict(int)\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] > 0:\n",
    "                    rootval[uf.find(x * n + y)] += grid[x][y]\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] > 0:\n",
    "                    ans += tot - rootval[uf.find(x * n + y)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        size,total=n*n,0\n",
    "        kkk=setUnion(size)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    for a,b in [(-1,0),(0,-1)]:\n",
    "                        cur_i,cur_j=i+a,j+b\n",
    "                        if cur_i<0 or cur_j<0 or grid[cur_i][cur_j]==-1:\n",
    "                            continue\n",
    "                        kkk.union(i*n+j,cur_i*n+cur_j)\n",
    "                    total+=grid[i][j] \n",
    "        x=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x[kkk.find(i*n+j)]+=grid[i][j] if grid[i][j]>0 else 0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    ans+=total-x[kkk.find(i*n+j)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        size,total=n*n,0\n",
    "        kkk=setUnion(size)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    for a,b in [(-1,0),(0,-1)]:\n",
    "                        cur_i,cur_j=i+a,j+b\n",
    "                        if cur_i<0 or cur_j<0 or grid[cur_i][cur_j]==-1:\n",
    "                            continue\n",
    "                        kkk.union(i*n+j,cur_i*n+cur_j)\n",
    "                    total+=grid[i][j] \n",
    "        x=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x[kkk.find(i*n+j)]+=grid[i][j] if grid[i][j]>0 else 0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    ans+=total-x[kkk.find(i*n+j)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFindArray:\n",
    "    \"\"\"元素是0-n-1的并查集写法,不支持动态添加\n",
    "\n",
    "    初始化的连通分量个数 为 n\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\"n\", \"part\", \"_parent\", \"_rank\")\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self._parent = list(range(n))\n",
    "        self._rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        while self._parent[x] != x:\n",
    "            self._parent[x] = self._parent[self._parent[x]]\n",
    "            x = self._parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        \"\"\"按秩合并.\"\"\"\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        if self._rank[rootX] > self._rank[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def unionTo(self, child: int, parent: int) -> bool:\n",
    "        \"\"\"定向合并.将child的父节点设置为parent.\"\"\"\n",
    "        rootX = self.find(child)\n",
    "        rootY = self.find(parent)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def unionWithCallback(self, x: int, y: int, f: Callable[[int, int], None]) -> bool:\n",
    "        \"\"\"\n",
    "        f: 合并后的回调函数, 入参为 (big, small)\n",
    "        \"\"\"\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        if self._rank[rootX] > self._rank[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        f(rootY, rootX)\n",
    "        return True\n",
    "\n",
    "    def isConnected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def getGroups(self) -> DefaultDict[int, List[int]]:\n",
    "        groups = defaultdict(list)\n",
    "        for key in range(self.n):\n",
    "            root = self.find(key)\n",
    "            groups[root].append(key)\n",
    "        return groups\n",
    "\n",
    "    def getRoots(self) -> List[int]:\n",
    "        return list(set(self.find(key) for key in self._parent))\n",
    "\n",
    "    def getSize(self, x: int) -> int:\n",
    "        return self._rank[self.find(x)]\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return \"\\n\".join(f\"{root}: {member}\" for root, member in self.getGroups().items())\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self.part\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        ROW, COL = len(grid), len(grid[0])\n",
    "        uf = UnionFindArray(ROW * COL)\n",
    "        for r in range(ROW):\n",
    "            for c in range(COL):\n",
    "                if grid[r][c] == -1:\n",
    "                    continue\n",
    "                if r > 0 and grid[r - 1][c] != -1:\n",
    "                    uf.union(r * COL + c, (r - 1) * COL + c)\n",
    "                if c > 0 and grid[r][c - 1] != -1:\n",
    "                    uf.union(r * COL + c, r * COL + c - 1)\n",
    "\n",
    "        groups = uf.getGroups()\n",
    "        groupSum = defaultdict(int)\n",
    "        for root, members in groups.items():\n",
    "            if grid[root // COL][root % COL] == -1:\n",
    "                continue\n",
    "            for member in members:\n",
    "                groupSum[root] += grid[member // COL][member % COL]\n",
    "        allSum = sum(groupSum.values(), 0)\n",
    "\n",
    "        res = 0\n",
    "        for r in range(ROW):\n",
    "            for c in range(COL):\n",
    "                if grid[r][c] != -1:\n",
    "                    res += allSum - groupSum[uf.find(r * COL + c)]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFindArray:\n",
    "    \"\"\"元素是0-n-1的并查集写法,不支持动态添加\n",
    "\n",
    "    初始化的连通分量个数 为 n\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\"n\", \"part\", \"_parent\", \"_rank\")\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self._parent = list(range(n))\n",
    "        self._rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        while self._parent[x] != x:\n",
    "            self._parent[x] = self._parent[self._parent[x]]\n",
    "            x = self._parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        \"\"\"按秩合并.\"\"\"\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        if self._rank[rootX] > self._rank[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def unionTo(self, child: int, parent: int) -> bool:\n",
    "        \"\"\"定向合并.将child的父节点设置为parent.\"\"\"\n",
    "        rootX = self.find(child)\n",
    "        rootY = self.find(parent)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def unionWithCallback(self, x: int, y: int, f: Callable[[int, int], None]) -> bool:\n",
    "        \"\"\"\n",
    "        f: 合并后的回调函数, 入参为 (big, small)\n",
    "        \"\"\"\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        if self._rank[rootX] > self._rank[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self._parent[rootX] = rootY\n",
    "        self._rank[rootY] += self._rank[rootX]\n",
    "        self.part -= 1\n",
    "        f(rootY, rootX)\n",
    "        return True\n",
    "\n",
    "    def isConnected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def getGroups(self) -> DefaultDict[int, List[int]]:\n",
    "        groups = defaultdict(list)\n",
    "        for key in range(self.n):\n",
    "            root = self.find(key)\n",
    "            groups[root].append(key)\n",
    "        return groups\n",
    "\n",
    "    def getRoots(self) -> List[int]:\n",
    "        return list(set(self.find(key) for key in self._parent))\n",
    "\n",
    "    def getSize(self, x: int) -> int:\n",
    "        return self._rank[self.find(x)]\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return \"\\n\".join(f\"{root}: {member}\" for root, member in self.getGroups().items())\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self.part\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        ROW, COL = len(grid), len(grid[0])\n",
    "        uf = UnionFindArray(ROW * COL)\n",
    "        for r in range(ROW):\n",
    "            for c in range(COL):\n",
    "                if grid[r][c] == -1:\n",
    "                    continue\n",
    "                if r > 0 and grid[r - 1][c] != -1:\n",
    "                    uf.union(r * COL + c, (r - 1) * COL + c)\n",
    "                if c > 0 and grid[r][c - 1] != -1:\n",
    "                    uf.union(r * COL + c, r * COL + c - 1)\n",
    "\n",
    "        groups = uf.getGroups()\n",
    "        groupSum = defaultdict(int)\n",
    "        for root, members in groups.items():\n",
    "            if grid[root // COL][root % COL] == -1:\n",
    "                continue\n",
    "            for member in members:\n",
    "                groupSum[root] += grid[member // COL][member % COL]\n",
    "        allSum = sum(groupSum.values())\n",
    "\n",
    "        res = 0\n",
    "        for r in range(ROW):\n",
    "            for c in range(COL):\n",
    "                if grid[r][c] != -1:\n",
    "                    res += allSum - groupSum[uf.find(r * COL + c)]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=n*n\n",
    "        pa=list(range(m))\n",
    "        def find(k):\n",
    "            if pa[k]!=k:\n",
    "                pa[k]=find(pa[k])\n",
    "            return pa[k]\n",
    "        def union(x,y):\n",
    "            px,py=find(x),find(y)\n",
    "            if px==py:return \n",
    "            pa[py]=px\n",
    "        als=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==-1:continue\n",
    "                als+=grid[i][j]\n",
    "                if i+1<n and grid[i+1][j]!=-1:union(i*n+j,i*n+n+j)\n",
    "                if j+1<n and grid[i][j+1]!=-1:union(i*n+j,i*n+j+1)\n",
    "        rk=[als]*m\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=-1:rk[find(i*n+j)]-=grid[i][j]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=-1:res+=rk[find(i*n+j)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=n*n\n",
    "        pa=list(range(m))\n",
    "        def find(k):\n",
    "            if pa[k]!=k:\n",
    "                pa[k]=find(pa[k])\n",
    "            return pa[k]\n",
    "        def union(x,y):\n",
    "            px,py=find(x),find(y)\n",
    "            if px==py:return \n",
    "            pa[py]=px\n",
    "        als=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==-1:continue\n",
    "                als+=grid[i][j]\n",
    "                if i+1<n and grid[i+1][j]!=-1:\n",
    "                    union(i*n+j,i*n+n+j)\n",
    "                if j+1<n and grid[i][j+1]!=-1:\n",
    "                    union(i*n+j,i*n+j+1)\n",
    "        rk=[als]*m\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==-1:continue\n",
    "                rk[find(i*n+j)]-=grid[i][j]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==-1:continue\n",
    "                res+=rk[find(i*n+j)]\n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        sm = 0\n",
    "        cnt = 0\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        parent = list(range(m*n))\n",
    "        table = {}  \n",
    "        \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]!=-1:\n",
    "                    cnt+=1\n",
    "                    sm+=grid[r][c]\n",
    "                    if r and grid[r-1][c]!=-1:\n",
    "                        union(r*n+c,(r-1)*n+c)\n",
    "                    if c and grid[r][c-1]!=-1:\n",
    "                        union(r*n+c,r*n+c-1)\n",
    "        \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]!=-1:\n",
    "                    p = find(r*n+c)\n",
    "                    if p in table:\n",
    "                        table[p][0]+=grid[r][c]\n",
    "                        table[p][1]+=1\n",
    "                    else:\n",
    "                        table[p]=[grid[r][c],1]\n",
    "        \n",
    "        return sum(table[ke][0]*(cnt-table[ke][1]) for ke in table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]        \n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    sm, x = sm + grid[i][j], i*n+j\n",
    "                    dc[x], has[x] = x, grid[i][j]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                            y = find(nx*n+ny)\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]        \n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    sm, x = sm + grid[i][j], i*n+j\n",
    "                    dc[x], has[x] = x, grid[i][j]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                            y = find(nx*n+ny)\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def find(x):\n",
    "\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "\n",
    "            return dc[x]        \n",
    "\n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\n",
    "\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\n",
    "\n",
    "        for i in range(m):\n",
    "\n",
    "            for j in range(n):\n",
    "\n",
    "                if grid[i][j] > 0:\n",
    "\n",
    "                    sm, x = sm + grid[i][j], i*n+j\n",
    "\n",
    "                    dc[x], has[x] = x, grid[i][j]\n",
    "\n",
    "                    for dx, dy in POS:\n",
    "\n",
    "                        nx, ny = i + dx, j + dy\n",
    "\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "\n",
    "                            y = find(nx*n+ny)\n",
    "\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\n",
    "\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]        \n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    sm, x = sm + grid[i][j], i*n+j\n",
    "                    dc[x], has[x] = x, grid[i][j]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                            y = find(nx*n+ny)\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]        \n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    sm, x = sm + grid[i][j], i*n+j\n",
    "                    dc[x], has[x] = x, grid[i][j]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                            y = find(nx*n+ny)\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\r\n",
    "        def find(x):\r\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\r\n",
    "            return dc[x]        \r\n",
    "        m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0\r\n",
    "        has, dc = [-1] * (m*n), [-1] * (m*n)\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] > 0:\r\n",
    "                    sm, x = sm + grid[i][j], i*n+j\r\n",
    "                    dc[x], has[x] = x, grid[i][j]\r\n",
    "                    for dx, dy in POS:\r\n",
    "                        nx, ny = i + dx, j + dy\r\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\r\n",
    "                            y = find(nx*n+ny)\r\n",
    "                            if x != y: dc[y], has[x] = x, has[x] + has[y]\r\n",
    "        for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        total_visited = set()\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        total_sum = 0\n",
    "        lst = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] > -1 and (i, j) not in total_visited:\n",
    "                    queue = deque([(i, j)])\n",
    "                    visited = {(i, j)}\n",
    "                    while queue:\n",
    "                        cur_i, cur_j = queue.popleft()\n",
    "                        for di, dj in directions:\n",
    "                            nxt_i, nxt_j = cur_i + di, cur_j + dj\n",
    "                            if not (0 <= nxt_i < row and 0 <= nxt_j < col):\n",
    "                                continue\n",
    "                            if (nxt_i, nxt_j) in visited or grid[nxt_i][nxt_j] == -1:\n",
    "                                continue\n",
    "                            visited.add((nxt_i, nxt_j))\n",
    "                            queue.append((nxt_i, nxt_j))\n",
    "                    s = 0\n",
    "                    for ii, jj in visited:\n",
    "                        s += grid[ii][jj]\n",
    "                        total_visited.add((ii, jj))\n",
    "                    total_sum += s\n",
    "                    lst.append([len(visited), s])\n",
    "        ans = 0\n",
    "        for count, s in lst:\n",
    "            ans += count * (total_sum - s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        total_visited = set()\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        total_sum = 0\n",
    "        lst = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] > -1 and (i, j) not in total_visited:\n",
    "                    queue = deque([(i, j)])\n",
    "                    visited = {(i, j)}\n",
    "                    while queue:\n",
    "                        cur_i, cur_j = queue.popleft()\n",
    "                        for di, dj in directions:\n",
    "                            nxt_i, nxt_j = cur_i + di, cur_j + dj\n",
    "                            if not (0 <= nxt_i < row and 0 <= nxt_j < col):\n",
    "                                continue\n",
    "                            if (nxt_i, nxt_j) in visited or grid[nxt_i][nxt_j] == -1:\n",
    "                                continue\n",
    "                            visited.add((nxt_i, nxt_j))\n",
    "                            queue.append((nxt_i, nxt_j))\n",
    "                    s = 0\n",
    "                    for ii, jj in visited:\n",
    "                        s += grid[ii][jj]\n",
    "                        total_visited.add((ii, jj))\n",
    "                    total_sum += s\n",
    "                    lst.append([len(visited), s])\n",
    "        ans = 0\n",
    "        for count, s in lst:\n",
    "            ans += count * (total_sum - s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\r\n",
    "        row = len(grid)\r\n",
    "        col = len(grid[0])\r\n",
    "        total_visited = set()\r\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\r\n",
    "        total_sum = 0\r\n",
    "        lst = []\r\n",
    "        for i in range(row):\r\n",
    "            for j in range(col):\r\n",
    "                if grid[i][j] > -1 and (i, j) not in total_visited:\r\n",
    "                    queue = deque([(i, j)])\r\n",
    "                    visited = {(i, j)}\r\n",
    "                    while queue:\r\n",
    "                        cur_i, cur_j = queue.popleft()\r\n",
    "                        for di, dj in directions:\r\n",
    "                            nxt_i, nxt_j = cur_i + di, cur_j + dj\r\n",
    "                            if not (0 <= nxt_i < row and 0 <= nxt_j < col):\r\n",
    "                                continue\r\n",
    "                            if (nxt_i, nxt_j) in visited or grid[nxt_i][nxt_j] == -1:\r\n",
    "                                continue\r\n",
    "                            visited.add((nxt_i, nxt_j))\r\n",
    "                            queue.append((nxt_i, nxt_j))\r\n",
    "                    s = 0\r\n",
    "                    for ii, jj in visited:\r\n",
    "                        s += grid[ii][jj]\r\n",
    "                        total_visited.add((ii, jj))\r\n",
    "                    total_sum += s\r\n",
    "                    lst.append([len(visited), s])\r\n",
    "        ans = 0\r\n",
    "        for count, s in lst:\r\n",
    "            ans += count * (total_sum - s)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        \n",
    "        has = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dc = [-1] * (m*n)\n",
    "        POS = ((0, -1), (-1, 0))\n",
    "        sm = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    sm += grid[i][j]\n",
    "                    x = i*n+j\n",
    "                    dc[x] = x\n",
    "                    has[x] = grid[i][j]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                            y = find(nx*n+ny)\n",
    "                            if x != y:\n",
    "                                dc[y] = x\n",
    "                                has[x] += has[y]\n",
    "        res = 0\n",
    "        # print(sm, has)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    res += sm - has[find(i*n+j)]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    count, and modify the origin graph\n",
    "    - the same region has the same value\n",
    "    - the region and region count\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        temp = [] #[[sum, count]]\n",
    "        s = 0\n",
    "        def dfs(x: int, y: int):\n",
    "            nonlocal s\n",
    "            for i in range(4):\n",
    "                if x + dx[i] >= 0 and x + dx[i] < r and y + dy[i] >= 0 and y + dy[i] < c and grid[x + dx[i]][y + dy[i]] > 0:\n",
    "                    temp[-1][0] += grid[x + dx[i]][y + dy[i]]\n",
    "                    temp[-1][1] += 1\n",
    "                    s += grid[x + dx[i]][y + dy[i]]\n",
    "                    grid[x + dx[i]][y + dy[i]] = -1\n",
    "                    dfs(x + dx[i], y + dy[i])\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] > 0:\n",
    "                    temp.append([grid[i][j], 1])\n",
    "                    s += grid[i][j]\n",
    "                    grid[i][j] = -1\n",
    "                    dfs(i, j)\n",
    "        res = 0\n",
    "        for i in temp:\n",
    "            res += (s - i[0]) * i[1]\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        n = len(grid)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    cnt += 1\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            s, c = 0, 0\n",
    "            if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] == -1:\n",
    "                return 0, 0\n",
    "            s += grid[i][j]\n",
    "            c += 1\n",
    "            grid[i][j] = -1\n",
    "            for d in dirs:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                t1, t2 = dfs(x, y)\n",
    "                s += t1\n",
    "                c += t2\n",
    "            return s, c\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    s, c = dfs(i, j)\n",
    "                    ans += s * (cnt - c)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        n = len(grid)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    cnt += 1\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            s, c = 0, 0\n",
    "            if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] == -1:\n",
    "                return 0, 0\n",
    "\n",
    "            s += grid[i][j]\n",
    "            c += 1\n",
    "            grid[i][j] = -1\n",
    "            for d in dirs:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                t1, t2 = dfs(x, y)\n",
    "                s += t1\n",
    "                c += t2\n",
    "\n",
    "            return s, c\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    s, c = dfs(i, j)\n",
    "                    ans += s * (cnt - c)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        n = len(grid)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    cnt += 1\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            s, c = 0, 0\n",
    "            if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] == -1:\n",
    "                return 0, 0\n",
    "\n",
    "            s += grid[i][j]\n",
    "            c += 1\n",
    "            grid[i][j] = -1\n",
    "            for d in dirs:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                t1, t2 = dfs(x, y)\n",
    "                s += t1\n",
    "                c += t2\n",
    "\n",
    "            return s, c\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != -1:\n",
    "                    s, c = dfs(i, j)\n",
    "                    ans += s * (cnt - c)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i: int, j: int) -> (int, int):\n",
    "            s, t = grid[i][j], 1\n",
    "            grid[i][j] = 0\n",
    "            for a, b in pairwise(dirs):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] > 0:\n",
    "                    s1, t1 = dfs(x, y)\n",
    "                    s, t = s + s1, t + t1\n",
    "            return s, t\n",
    "\n",
    "        n = len(grid)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        cnt = sum(x > 0 for row in grid for x in row)\n",
    "        ans = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x > 0:\n",
    "                    s, t = dfs(i, j)\n",
    "                    ans += (cnt - t) * s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def f(i, j):\n",
    "            val, cnt, grid[i][j] = grid[i][j], 1, -1\n",
    "            for i1, j1 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0 <= i1 < m and 0 <= j1 < n and grid[i1][j1] >= 0:\n",
    "                    v, c = f(i1, j1)\n",
    "                    val += v\n",
    "                    cnt += c\n",
    "            return val, cnt\n",
    "        vc = nc = sc = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    v, c = f(i, j)\n",
    "                    vc += v\n",
    "                    nc += c\n",
    "                    sc += v * c\n",
    "        return vc * nc - sc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        def dfs(i,j):\n",
    "            sm,cnt = grid[i][j],1\n",
    "            grid[i][j]=-1\n",
    "            for i2,j2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0<=i2<m and 0<=j2<n and grid[i2][j2]>=0:\n",
    "                    sm2,cnt2= dfs(i2,j2)\n",
    "                    sm+=sm2\n",
    "                    cnt+=cnt2\n",
    "            return sm,cnt\n",
    "        sms,cnts,smcnt = 0,0,0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>=0:\n",
    "                    sm,cnt = dfs(i,j)\n",
    "                    sms+=sm\n",
    "                    cnts+=cnt\n",
    "                    smcnt+=sm*cnt\n",
    "        return sms*cnts-smcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    # Find the root of the set to which x belongs\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def find_fast(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def get_grp(self):\n",
    "        m1 = defaultdict(list)\n",
    "        for k,v in enumerate(self.parent):\n",
    "            idx1 = self.find_fast(k)\n",
    "            m1[idx1].append(k)\n",
    "        return m1\n",
    "\n",
    "    # Union two sets represented by x and y\n",
    "    def union(self, x, y):\n",
    "        xroot = self.find(x)\n",
    "        yroot = self.find(y)\n",
    "\n",
    "        if xroot == yroot:\n",
    "            return\n",
    "\n",
    "        if self.rank[xroot] < self.rank[yroot]:\n",
    "            self.parent[xroot] = yroot\n",
    "        elif self.rank[xroot] > self.rank[yroot]:\n",
    "            self.parent[yroot] = xroot\n",
    "        else:\n",
    "            self.parent[yroot] = xroot\n",
    "            self.rank[xroot] += 1\n",
    "\n",
    "class Solution:\n",
    "    def sumRemoteness(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 != -1:\n",
    "                    cnt += v2\n",
    "\n",
    "        total = len(grid) * len(grid[0])\n",
    "        len1 = len(grid[0])\n",
    "        ds = DisjointSet(total)\n",
    "        todo = []\n",
    "        t1 = 0\n",
    "        cntM = {}\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                cntM[k * len1 + k2] = v2\n",
    "                if v2 == -1:\n",
    "                    continue\n",
    "                t1 += v2\n",
    "\n",
    "                if k > 0:\n",
    "                    if grid[k - 1][k2] != -1:\n",
    "                        ds.union(k * len1 + k2, (k - 1) * len1 + k2)\n",
    "                if k2 > 0:\n",
    "                    if grid[k][k2 - 1] != -1:\n",
    "                        ds.union(k * len1 + k2, k * len1 + k2 - 1)\n",
    "\n",
    "        cnt = 0\n",
    "        grp1 = ds.get_grp()\n",
    "        for i in grp1:\n",
    "            ll1 = grp1[i]\n",
    "            ttlist = []\n",
    "            for j in ll1:\n",
    "                if cntM[j] == -1:\n",
    "                    continue\n",
    "                ttlist.append(cntM[j])\n",
    "            ss2 = sum(ttlist)\n",
    "            cnt += (t1 - ss2) * len(ttlist)\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.sumRemoteness( [[-1,3,4],[-1,-1,-1],[3,-1,-1]] ))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
